//单词拆分
https://leetcode.cn/problems/word-break/description/?envType=problem-list-v2&envId=string

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) 
    {
        int n = s.size();
        string str = '-' + s;
        vector<bool> dp(n + 1);
        dp[0] = true;
        set<string> v(wordDict.begin(),wordDict.end());
        
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= i; j++)
            {
                bool ret = v.find(str.substr(j,i-j+1)) != v.end();
                if(dp[j - 1] && ret)
                {
                    dp[i] = true;
                }
            }
        }

        return dp.back();
    }
};
